2017년10월21일 6번
[과목 구분 없음] 다음 그래프의 정점 A에서부터 깊이 우선 탐색(DFS: Depth First Search)과 너비 우선 탐색(BFS: Breadth First Search)을 수행할 때, 방문 순서를 옳게 짝지은 것은? (단, 방문하지 않은 인접 정점이 2개 이상인 경우 알파벳 오름차순으로 방문한다)
- ① DFS : A-B-D-G-F-C-EBFS : A-B-C-D-E-F-G
- ② DFS : A-B-D-G-F-C-EBFS : A-B-C-D-E-G-F
- ③ DFS : A-B-D-G-E-C-FBFS : A-B-C-D-E-F-G
- ④ DFS : A-B-D-G-E-C-FBFS : A-B-C-D-E-G-F
(정답률: 50%)
문제 해설
DFS는 깊이 우선 탐색으로, 한 정점에서 시작하여 가능한 한 깊이 탐색한 후 다시 돌아와 다음 정점을 탐색하는 방식입니다. 따라서 A에서 시작하여 B로 이동한 후, B에서 D로 이동하여 G까지 탐색한 후 다시 돌아와 E를 탐색하고, 마지막으로 C와 F를 탐색합니다. 이에 따라 방문 순서는 A-B-D-G-E-C-F가 됩니다.
BFS는 너비 우선 탐색으로, 한 정점에서 시작하여 인접한 정점을 모두 탐색한 후 그 다음 인접한 정점을 탐색하는 방식입니다. 따라서 A에서 시작하여 B와 C를 탐색한 후, B에서 D와 E를 탐색하고, C에서 F를 탐색한 후 마지막으로 G를 탐색합니다. 이에 따라 방문 순서는 A-B-C-D-E-G-F가 됩니다.
따라서 정답은 "DFS : A-B-D-G-E-C-F, BFS : A-B-C-D-E-G-F"입니다.
BFS는 너비 우선 탐색으로, 한 정점에서 시작하여 인접한 정점을 모두 탐색한 후 그 다음 인접한 정점을 탐색하는 방식입니다. 따라서 A에서 시작하여 B와 C를 탐색한 후, B에서 D와 E를 탐색하고, C에서 F를 탐색한 후 마지막으로 G를 탐색합니다. 이에 따라 방문 순서는 A-B-C-D-E-G-F가 됩니다.
따라서 정답은 "DFS : A-B-D-G-E-C-F, BFS : A-B-C-D-E-G-F"입니다.
